/*
 * @lc app=leetcode.cn id=92 lang=typescript
 *
 * [92] 反转链表 II
 */

// @lc code=start
/**
 * Definition for singly-linked list.
 * class ListNode {
 *     val: number
 *     next: ListNode | null
 *     constructor(val?: number, next?: ListNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.next = (next===undefined ? null : next)
 *     }
 * }
 */
//  思路：关键是记录后驱节点，方便后续连接
//  注意递归的参数
//  参考：https://labuladong.github.io/algo/2/19/18/

//  复杂度：O(n) O(1)

let nextNode: ListNode | null

function reverseBetween(head: ListNode | null, left: number, right: number): ListNode | null {
    if (!head) return head
    if (left === 1) return reverseN(head, right)
    // 前进到反转的起点触发 base case
    head.next = reverseBetween(head.next, left - 1, right - 1)
    return head
};
// 反转链表前N个节点
function reverseN(head: ListNode | null, n: number): ListNode | null {
    if (!head) return head
    if (n === 1) {
        nextNode = head.next
        return head
    }
    const last = reverseN(head.next, n - 1)
    if (head.next) {
        head.next.next = head
        head.next = nextNode
    }
    return last
};
// @lc code=end

import { ListNode } from './type'

const head = new ListNode(1, new ListNode(2, new ListNode(3, new ListNode(4, new ListNode(5, new ListNode(6))))))

console.log(1, ListNode.printList(head));
// console.log(2, ListNode.printList(reverseN(head, 4)));
console.log(3, ListNode.printList(reverseBetween(head, 2, 4)));